/*


*/

class Solution {
public:
    // 主函数，计算在给定天数内运送所有包裹所需的最低运载能力
    int shipWithinDays(vector<int>& weights, int days) {
        int minCapacity = INT_MAX; // 初始化最低运载能力为最大整数
        int left = 1, right = 100000000; // 设置二分查找的左右边界

        // 使用二分查找来确定最低运载能力
        while (left < right) {
            int mid = left + (right - left) / 2; // 计算中间值
            int requiredDays = getRequiredDays(mid, weights); // 计算在当前运载能力下所需的天数

            // 如果所需天数大于给定天数或有单个包裹重量超过当前运载能力，则增加运载能力
            if (requiredDays == -1 || requiredDays > days) {
                left = mid + 1;
            } else {
                // 否则，尝试减小运载能力
                right = mid;
            }
        }

        return left; // 返回最低运载能力
    }

    // 辅助函数，计算在给定运载能力下所需的天数
    int getRequiredDays(int maxWeight, vector<int>& weights) {
        int days = 0; // 初始化所需天数
        int currentWeight = 0; // 当前船上的总重量

        // 遍历所有包裹
        for (int i = 0; i < weights.size(); i++) {
            // 如果有单个包裹的重量超过当前运载能力，返回 -1 表示无法完成任务
            if (weights[i] > maxWeight) {
                return -1;
            }

            // 累加当前船上的总重量
            currentWeight += weights[i];

            // 如果当前船上的总重量超过运载能力，则需要新的一天来运送剩余包裹
            if (currentWeight > maxWeight) {
                days++;
                currentWeight = weights[i]; // 重置当前船上的总重量为当前包裹的重量
            }
        }

        // 如果当前船上的总重量大于 0，还需要额外的一天来运送这些包裹
        if (currentWeight > 0) {
            days++;
        }

        return days; // 返回所需的天数
    }
};